package arrays;

import java.util.*;

/**
 * @author LiangMu
 * @version \$Id: P13.java, v 0.1, 2022年12月14日 13:27 LiangMu Exp $$
 */
public class P13 {
    public static void main(String[] args) {
        int[][] ints = new int[][]{{1,3},{2,6},{8,10},{15,18}};
        int[][] merge = merge2(ints);
        for (int[] it : merge) {
            System.out.println(Arrays.toString(it));
        }
    }

    public static int[][] merge2(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(val -> val[0]));
        Stack<int[]> stack = new Stack<>();
        for (int[] it : intervals) {
            if (stack.isEmpty()) {
                stack.push(it);
                continue;
            }
            int[] peek = stack.peek();
            if (peek[1] >= it[0]) {
                if (peek[1] < it[1]) {
                    peek[1] = it[1];
                }
            } else {
                stack.push(it);
            }
        }
        return stack.toArray(new int[0][0]);
    }

    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(v -> v[1]));
        Stack<int[]> stack = new Stack<>();
        for (int[] it : intervals) {
            if (!stack.isEmpty()) {
                while (!stack.isEmpty()) {
                    int[] peek = stack.peek();
                    if (peek[0] > it[0]) {
                        stack.pop();
                        continue;
                    }
                    if (peek[1] >= it[0]) {
                        peek[1] = it[1];
                    } else {
                        stack.push(it);
                    }
                    break;
                }
                if (stack.isEmpty()) {
                    stack.push(it);
                }
            } else {
                stack.push(it);
            }
        }
        return new ArrayList<>(stack).toArray(new int[0][0]);
    }
}
